package org.TheSubject;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须 原地 修改，只允许使用额外常数空间
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution31OfHot {
    public void nextPermutation(int[] nums) {
        int size=nums.length;
        if(size<=1){
            return;
        }
        this.nums=nums;
        int i=size-2;
        while(i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if(i>=0){
            int j=size-1;
            while (nums[j]<=nums[i]){
                j--;
            }
            this.sweap(i,j);
        }
        reverse(i+1);
    }
    private int[] nums;
    public void sweap(int left,int right){
        if (left==right){
            return;
        }
        int x=nums[left];
        nums[left]=nums[right];
        nums[right]=x;
    }
    public void reverse(int start){
        int left=start;
        int right=nums.length-1;
        while (left<right){
            this.sweap(left,right);
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Solution31OfHot solution31OfHot = new Solution31OfHot();
        int[] test={1,2,3};
        solution31OfHot.nextPermutation(test);
        for (int i:
            test ) {
            System.out.print(i+",");
        }
    }
}
